class Permutation:
    """排列组合计算器"""

    def __init__(self, mod: int = 10 ** 9 + 7):
        self._mod = mod
        self._size = 0
        self._cache_factorial = [1]  # 缓存阶乘
        self._cache_factorial_inv = [1]  # 缓存阶乘的乘法逆元

    def factorial(self, n: int) -> int:
        """计算阶乘：n!"""
        while self._size <= n:
            self._size += 1
            self._cache_factorial.append((self._cache_factorial[-1] * self._size) % self._mod)
            self._cache_factorial_inv.append(pow(self._cache_factorial[-1], self._mod - 2, self._mod))
        return self._cache_factorial[n]

    def arrange(self, n: int, m: int) -> int:
        """计算排列数：A(n,m) (n>=m)"""
        return (self.factorial(n) * self._cache_factorial_inv[n - m]) % self._mod

    def comb(self, n: int, m: int) -> int:
        """计算组合数：C(n,m) (n>=m)"""
        return (self.arrange(n, m) * self._cache_factorial_inv[m]) % self._mod


if __name__ == "__main__":
    permutation = Permutation()
    print(permutation.factorial(5))  # 120
    print(permutation.arrange(4, 2))  # 12
    print(permutation.comb(6, 2))  # 15
    print(permutation.comb(17, 15))  # 136
    print(permutation.comb(17, 2))  # 136
    print(permutation.comb(135, 8))  # 919468422
